package graph_viewer.util;

import java.awt.Graphics;
import java.awt.FontMetrics;
import java.awt.Font;
import java.util.ArrayList;
import java.util.Iterator;

import graph_viewer.drawer.*;
import graph_viewer.structure.*;
import graph_viewer.layout.*;

public class Structure_Util{
	static public Node find_graph_root( Graph a_graph ){
		return a_graph.find_tree().get_root();
	}

	static public int find_default_node_width(){
		int	default_width	= Layout.DEFAULT_NODE_WIDTH;
		return default_width;
		
		/*double	random_width	= Math.random() * default_width;

		int	minimum_width	= 30;

		if ( random_width < minimum_width ){
			random_width = minimum_width;
		}

		return (int)random_width;
		*/
	}

	static public int find_default_node_height(){
		int default_height	= Layout.DEFAULT_NODE_HEIGHT;		

		double random_height	= Math.random() * default_height;

		int	minimum_height	= 25;

		if ( random_height < minimum_height ){
			random_height = minimum_height;
		}

		return (int)random_height;
	}

	static public int get_default_doi(){
		return Graph.DEFAULT_DOI;
	}

	public static boolean is_null_label( String a_label ){
		return a_label.equals( Visual_Component.NULL_LABEL );
	}

	static public boolean is_null_node( Node a_node ){
		return is_null_label( a_node.get_label() );
	}
	
	static public boolean is_tree( String graph_type ){
		return graph_type.equals( Visual_Component.TREE );
	}

	static public boolean is_clustered_graph( String graph_type ){
		return graph_type.equals( Visual_Component.CLUSTERED_GRAPH );
	}

	// travese a tree, do nothing but print out node's label
	public static void traverse_tree( Tree a_tree ){
		Out.println( "\ttraversing tree... " );
		Out.println( "\troot is " + a_tree.get_root());

		a_tree.traverse( 
			new Command(){
				public void do_action( Node node ){
					Debug.println( "\t[ " + node + " ]", 3 );
				}
			} 
		);

		Out.println( "\ttraversing tree finished. " );
	}

	//@return true if there is an edge between the two nodes
	public static boolean has_edge( Graph g, Node node_a, Node node_b ){
		ArrayList edges	= g.find_edges();

		String 
			a_label	= node_a.get_label(),
			b_label	= node_b.get_label();

		for ( Iterator _i = edges.iterator() ; _i.hasNext() ; ){
			String[] an_edge	= (String[])_i.next();
			String 
				start_label	= an_edge[0],
				end_label	= an_edge[1];

			if ( start_label.equals(a_label) ){
				if ( end_label.equals(b_label ) ){
					return true;
				}
			}

			if ( end_label.equals(a_label) ){
				if ( start_label.equals(b_label ) ){
					return true;
				}
			}

		}
		
		return false;
	}


	//not_closed_clusters are presented as (opened) clusters, not leaf, in the drawing of a clustered graph
	//public static ArrayList	find_not_closed_clusters( Graph g ){
	public static ArrayList find_opened_clusters( Graph g ){
		ArrayList not_closed_clusters	= new ArrayList();

		//for ( Iterator _i = g.find_nodes().iterator(); _i.hasNext(); ){
		for ( Iterator _i = g.find_nodes().iterator(); _i.hasNext(); ){
			Node a_node	= (Node)_i.next();
			
			if ( a_node.is_root() || a_node.is_leaf_cluster() ){
				continue;
			}else if ( !a_node.get_is_closed() ){
				not_closed_clusters.add( a_node );
			}
		}
	
		return not_closed_clusters;
	}

	public static boolean is_parent_of_leaf_clusters( Node node ){
		if ( node.get_is_closed() ){//a closed cluster definitely is not a parent of a _leaf cluster.
			return false;
		}
		
		ArrayList children = node.get_children();

		for ( Iterator _i=children.iterator(); _i.hasNext() ; ){
			Node child	= (Node)_i.next();

			if ( child.get_is_closed() ){ // if any child is closed, the node is a parent of a _leaf cluster.
				return true;
			}
		}
		
		return false;
	}
	

	public static void test_nodes_overlap( Graph graph ){
		ArrayList leaf_clusters = graph.find_leaf_clusters();
		
		Node first_leaf = (Node)leaf_clusters.get( 0 );
		
		Debug.println( "===========test " + first_leaf + " overlapping.===========", 3 );
		for ( Iterator _i = leaf_clusters.iterator(); _i.hasNext(); ){
			Node node = (Node)_i.next();
			
			if ( first_leaf.is_overlapped( node ) ){				
				Debug.println(first_leaf.get_label()  + " overlapped " + node.get_label(), 3 );
			}else{
				//Debug.println( node.get_label() + " NOT overlapped " + first_leaf.get_label(), 3 );				
				Debug.println(first_leaf.get_label()  + "NOT overlapped " + node.get_label(), 3 );
			}
		}
		
		Node second_leaf = (Node)leaf_clusters.get( 1 );
		Debug.println( "===========test " + second_leaf + " overlapping.===========", 3 );
		for ( Iterator _i = leaf_clusters.iterator(); _i.hasNext(); ){
			Node node = (Node)_i.next();
			
			if ( second_leaf.is_overlapped( node ) ){
				Debug.println(second_leaf.get_label()  + " overlapped " + node.get_label(), 3 );
			}else{
				//Debug.println( node.get_label() + " NOT overlapped " + second_leaf.get_label(), 3 );
				Debug.println( second_leaf + " NOT overlapped " + node, 3 );
			}
		}

		/*Node _3 = (Node)leaf_clusters.get( 2 );
		Debug.println( "===========test " + second_leaf + " overlapping.===========", 3 );
		for ( Iterator _i = leaf_clusters.iterator(); _i.hasNext(); ){
			Node node = (Node)_i.next();
			
			if ( _3.is_overlapped( node ) ){
				Debug.println(_3.get_label()  + " overlapped " + node.get_label(), 3 );
			}else{
				//Debug.println( node.get_label() + " NOT overlapped " + second_leaf.get_label(), 3 );
				Debug.println( _3 + " NOT overlapped " + node, 3 );
			}	
		}*/
	}
	
	//circle all disconnected children and joint the circle with a child whose degree is one.
	// by adding a psuedo edge between two nodes
	static public ArrayList create_disconnected_nodes_psuedo_edge( Node a_cluster, Graph a_graph ){
		ArrayList pseudo_edges			= new ArrayList();

		ArrayList disconnected_nodes	 = find_disconnected_nodes( a_cluster, a_graph );
		int number_of_disconnected_nodes	= disconnected_nodes.size();
		
		//Debug.println( " found " + number_of_disconnected_nodes + " disconnected_nodes under " + a_cluster , 3 );
		if ( number_of_disconnected_nodes == 0 ){
			return pseudo_edges;
		}

		for ( int i = 0; i < number_of_disconnected_nodes - 1 ; i ++ ){
			Node
				a_disconnected_child				= (Node)disconnected_nodes.get( i ),
				a_following_disconnected_child	= (Node)disconnected_nodes.get( i + 1 );
			
			Edge	an_edge	 = new Edge( a_disconnected_child, a_following_disconnected_child );
			
			pseudo_edges.add( an_edge );
		}
		


		if ( number_of_disconnected_nodes > 2 ){// two nodes need only one edge to be a circle.
			Node
				first_disconnected_child	= (Node)disconnected_nodes.get( 0 ),
				last_disconnected_node	= (Node)disconnected_nodes.get( number_of_disconnected_nodes - 1  );
					
			Edge	an_edge	 = new Edge( first_disconnected_child, last_disconnected_node );

			pseudo_edges.add( an_edge );			
		}
				
		Node lowest_degree_child = find_lowest_degree_child( a_cluster, a_graph );

		if ( lowest_degree_child != null ){//@see find_lowest_degree_child();
			Node
				first_disconnected_child	= (Node)disconnected_nodes.get( 0 ),
				last_disconnected_node	= (Node)disconnected_nodes.get( number_of_disconnected_nodes - 1  );
			
			Edge	an_edge	 = new Edge( first_disconnected_child, lowest_degree_child );
			pseudo_edges.add( an_edge );
			
			if ( number_of_disconnected_nodes > 1 ){
				Edge	another_edge	 = new Edge( last_disconnected_node, lowest_degree_child );
				pseudo_edges.add( an_edge );
			}
		}

		return pseudo_edges;
	}
	

	// @return the node whose degree is min, but not 0.
	// @return null if no node  whose degree is bigger than 0.
	static public Node find_lowest_degree_child( Node a_cluster, Graph a_graph ){
		int min_degree	 = Public_Values.MAX_INT;
		Node lowest_degree_child = null;

		for (  Iterator _i = a_cluster.get_children().iterator(); _i.hasNext(); ){
			Node child	= (Node)_i.next();
			
			int degree_of_child	= a_graph.degree( child );

			if ( degree_of_child < min_degree && degree_of_child > 0 ){
				lowest_degree_child = child;
				min_degree = degree_of_child;
			}
		}

		return lowest_degree_child;
	}
	
	static public ArrayList find_disconnected_nodes( Node a_cluster, Graph a_graph ){
		ArrayList disconnected_nodes = new ArrayList();

		for (  Iterator _i = a_cluster.get_children().iterator(); _i.hasNext(); ){
			Node child	= (Node)_i.next();
			int degree	= a_graph.inside_cluster_degree( child );

			//Debug.println( "degree of " + child + " is " + degree, 3 );
			if ( a_graph.degree( child ) == 0 ){
				disconnected_nodes.add( child );
			}
		}/**/

		return disconnected_nodes;
	}
	
	static public ArrayList find_displayed_edges( Graph graph ){
		ArrayList	 displayed_edges	= new ArrayList();
		
		Tree			tree				= graph.find_tree();
		ArrayList		leaf_clusters		= graph.find_leaf_clusters(  );
		ArrayList		edges	 		= graph.find_edges();

		for ( Iterator _i = edges.iterator(); _i.hasNext(); ){
			String[]	edge	= (String[])_i.next();
			String	 
				start_node_label	= edge[0],
				end_node_label	= edge[1];

			Node	
				start_node	= graph.search( start_node_label),
				end_node	= graph.search( end_node_label	);
			
			//start_node/end_node is definitely leaf nodes.
			//if it's not a leaf_cluster, then its parent is closed.
			// find its ancestor that is a leaf cluster
			String 
				new_start_nodes_label	= start_node_label,
				new_end_nodes_label	= end_node_label;

			if ( !start_node.is_leaf_cluster() ){
				for ( Iterator _j = leaf_clusters.iterator(); _j.hasNext(); ){
					Node leaf_cluster	= (Node)_j.next();

					if ( tree.is_ancestor( leaf_cluster, start_node ) ){
						new_start_nodes_label = leaf_cluster.get_label();
						break;
					}
				}
			}

			if ( !end_node.is_leaf_cluster() ){
				for ( Iterator _j = leaf_clusters.iterator(); _j.hasNext(); ){
					Node leaf_cluster	= (Node)_j.next();

					if ( tree.is_ancestor( leaf_cluster, end_node ) ){
						new_end_nodes_label = leaf_cluster.get_label();
						break;
					}
				}
			}
			if (! new_start_nodes_label.equals( new_end_nodes_label) ){
				String[] new_edge = new String[]{ new_start_nodes_label, new_end_nodes_label};

				displayed_edges.add( new_edge );
			}

		}

		return displayed_edges;
	}
	
	

}//:~
